//
// Created by madison on 2022/7/19.
//

#include "stack"

using namespace std;

/**
 * Definition for a binary tree node.
 **/
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    // 方法一: 递归
    bool helper(TreeNode *root, long long lower, long long upper) {
        if (root == nullptr) {
            return true;
        }
        if (root->val <= lower || root->val >= upper) {
            return false;
        }
        return helper(root->left, lower, root->val) && helper(root->right, root->val, upper);
    }

    bool isValidBST(TreeNode *root) {
        return helper(root, LONG_MIN, LONG_MAX);
    }

    // 方法二：中序遍历
    bool isValidBST1(TreeNode *root) {
        stack<TreeNode *> stack;
        long long inorder = (long long) INT_MIN - 1;
        while (!stack.empty() || root != nullptr) {
            while (root != nullptr) {
                stack.push(root);
                root = root->left;
            }
            root = stack.top();
            stack.pop();
            // 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
            if (root->val <= inorder) {
                return false;
            }
            inorder = root->val;
            root = root->right;
        }
        return true;
    }
};

int main() {
    TreeNode *node3 = new TreeNode(15);
    TreeNode *node4 = new TreeNode(7);

    TreeNode *node1 = new TreeNode(9);
    TreeNode *node2 = new TreeNode(20, node3, node4);

    TreeNode *root = new TreeNode(3, node1, node2);

    Solution solution;
    printf("%d", solution.isValidBST(root));
    return 0;
}